Ciencia de Datos

Víctor Muñiz Sánchez Maestría en Cómputo Estadístico

Spectral embeddings

Ejemplo 1

import matplotlib.pyplot as plt
import seaborn as sns
import importlib

sns.set()
%matplotlib inline
%load_ext autoreload
%autoreload 2

import os
from spectral_clustering import *

def plot_graph(X, knn_graph, data_toy=None, palet=None):    
    # crea los indices
    a, b = np.where(knn_graph>0)
    indices_temp = np.array([a,b]).T
    ix = indices_temp
    for i in range(indices_temp.shape[0]):
        test_elem = indices_temp[i,]
        temp = np.sum(np.isin(indices_temp,test_elem),axis=1)
        ix[temp==2,] = test_elem
        
    indices = np.unique(ix,axis=0)
    leg = 'brief'
    hue = 'cl'

    if data_toy is None:
        data_toy = pd.DataFrame(X)
        data_toy.columns = ['x1','x2']  
        data_toy = pd.DataFrame(data_toy).assign(cl = y)
        palet = None #['black']
        leg = None
        hue = None
    
    #fig, ax = plt.subplots(figsize=(8,8))
    sns.relplot(x='x1', y='x2', data = data_toy, hue= hue, palette=palet, s=150,legend = leg)
    #sns.scatterplot(x='x1', y='x2', data = data_toy, hue='cl', palette=palet, s=50,legend = 'brief')
    #for i in range(X.shape[0]):
    #    plt.text(X[i,0], X[i,1]+.1, i)
    
    for i in range(indices.shape[0]):
        coords = np.array([X[indices[i,0],:], X[indices[i,1],:]])
        #sns.lineplot(coords.T[0,], coords.T[1,], color='black',ax=ax)
        plt.plot(coords.T[0,], coords.T[1,], color='black')

ndata = 150
X, y, custom_palette, kclust = get_dataset('dona', ndata)

data_toy = pd.DataFrame(X)
data_toy.columns = ['x1','x2']
data_toy = pd.DataFrame(data_toy).assign(cl = y)
sns.relplot(x='x1', y='x2', data = data_toy, s=60, height=5)
plt.title('Datos sintéticos', fontsize=10);

Parámetros para clústering espectral

knn = 3 # k-vecinos cercanos para la construcción del grafo
sigma = 1.5 # sigma del Kernel Gaussiano
lflag = 'L' # Tipo de Laplaciano

Realiza el embedding de los datos según el Laplaciano inducido por el grafo construido

indices, knn_graph = graph(X,knn,mutual=False)
W = adjacency_matrix(X, knn_graph, sigma, True)
L, D = laplacian(W, flag=lflag)
vals, vecs, vecs_k = eigen_Lap(L,kclust,lflag)

El grafo creado

plot_graph(X,knn_graph)

Detalle con el grafo. Cuando usamos $k-$nn induce un grafo dirigido, por lo tanto, no es simétrico. Dos formas de solucionarlo es:

• ignorar las direcciones y considerar conexiones simétricas
• conexiones mútuas

Matriz de Adyacencias o Afinidad

plt.figure(figsize=(6,4))
sns.heatmap(knn_graph, cmap="YlGnBu");

Matriz de adyacencias (afinidad) sin pesos. Solo muestra los componentes están conectados

plt.figure(figsize=(6,4))
sns.heatmap(W, cmap="YlGnBu");

Matriz de adyacencias (afinidad) pesada usando distancia Gaussiana, es decir, con pesos $w_{i,j}=e^{\frac{-\Vert \mathbf{x}_i-\mathbf{x}_j \Vert^2}{2\sigma^2}}$ si $\mathbf{x}_i$ y $\mathbf{x}_j$ se conectan.

Análisis espectral. Observa el tipo de Laplaciano que usamos ($L$, $L_{\text{sym}}$ ó $L_{\text{rw}}$)

nv = 10
fig = plt.figure(figsize=(15,15))
plt.subplots_adjust(hspace = .5)
fig.add_subplot(321)
plt.title('valores propios', fontsize=14)
plt.scatter(range(nv),vals[:nv])
fig.add_subplot(322)
plt.title('eigenvector 1', fontsize=14)
data_vecs = pd.DataFrame(dict(x1=range(vecs.shape[0]),x2=vecs[:,0],cl=y))
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette, legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(323)
data_vecs = pd.DataFrame(dict(x1=range(vecs.shape[0]),x2=vecs[:,1],cl=y))
plt.title('eigenvector 2', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(324)
data_vecs = pd.DataFrame(dict(x1=range(vecs.shape[0]),x2=vecs[:,2],cl=y))
plt.title('eigenvector 3', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(325)
data_vecs = pd.DataFrame(dict(x1=range(vecs.shape[0]),x2=vecs[:,3],cl=y))
plt.title('eigenvector 4', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(326)
data_vecs = pd.DataFrame(dict(x1=range(vecs.shape[0]),x2=vecs[:,4],cl=y))
plt.title('eigenvector 5', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True);

Variación y/o inestabilidad numérica

Debemos considerar el error numérico que puede surgir en éstos métodos, particularmente los basados en descomposiciones espectrales de matrices con estructuras determinadas.

Observa los resultados haciendo un simple redondeo

rvals = np.round(vals,3)
rvecs = np.round(vecs,3)

nv = 10
fig = plt.figure(figsize=(15,15))
plt.subplots_adjust(hspace = .5)
fig.add_subplot(321)
plt.title('valores propios', fontsize=14)
plt.scatter(range(nv),rvals[:nv])
fig.add_subplot(322)
plt.title('eigenvector 1', fontsize=14)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,0],cl=y))
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette, legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(323)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,1],cl=y))
plt.title('eigenvector 2', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(324)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,2],cl=y))
plt.title('eigenvector 3', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(325)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,3],cl=y))
plt.title('eigenvector 4', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(326)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,4],cl=y))
plt.title('eigenvector 5', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True);

<Axes: title={'center': 'eigenvector 5'}, xlabel='x1', ylabel='x2'>

Ahora, observa los subgrafos que se identifican solamente con la información de los vectores propios del Laplaciano. En la gráfica se muestra con un círculo, el subgrafo formado con los valores más grandes del vector (indicador) propio correspondiente k_vec

k_vec = 0 #el subgrafo correspondiente a algún valor propio 0
vec_i = rvecs[:,k_vec]
un = np.unique(vec_i)
np.where(vec_i==un[0])[0]
ind_i = np.zeros(vec_i.shape)
for i in range(un.shape[0]):
    ind_i[np.where(vec_i==un[i])[0]] = i

data_spec = pd.DataFrame(dict(x1 = X[:,0], x2 = X[:,1], cl = ind_i))
plot_graph(X, knn_graph, data_toy = data_spec, palet = sns.color_palette(n_colors=len(un)))

zeros = pd.DataFrame(X).iloc[np.where(vec_i==np.max(vec_i))[0]]
plt.scatter(zeros.iloc[:,0], zeros.iloc[:,1], s=300, linewidth=1, facecolors = 'none', edgecolors='black');

Finalmente, realizamos $k-$means con el embedding obtenido

# kmeans
kmeans = cluster.KMeans(n_clusters=kclust, init='random',random_state=0, n_init = 'auto')
y_km = kmeans.fit_predict(vecs_k)
data_km = pd.DataFrame(dict(x1=X[:,0],x2=X[:,1],cl = y_km))

fig = plt.figure(figsize=(13,5))
fig.add_subplot(121)
plt.title('Spectral clustering')
sns.scatterplot(x='x1', y='x2', data = data_km, hue='cl', s=150, 
            palette = custom_palette,legend = 'brief')
fig.add_subplot(122)
plt.title('Original')
sns.scatterplot(x='x1', y='x2', hue = 'cl', data = data_toy, palette=custom_palette, s=150);

Ejemplo 2

ndata = 60
X, y, custom_palette, kclust = get_dataset('blobs', ndata)

data_toy = pd.DataFrame(X)
data_toy.columns = ['x1','x2']
data_toy = pd.DataFrame(data_toy).assign(cl = y)
sns.relplot(x='x1', y='x2', data = data_toy, height=5, s=60)
plt.title('Datos sintéticos', fontsize=10);

Parámetros para clústering espectral

knn = 5 # k-vecinos cercanos para la construcción del grafo
sigma = 1.5 # sigma del Kernel Gaussiano
lflag = 'L' # Tipo de Laplaciano

Realiza el embedding de los datos según el Laplaciano inducido por el grafo construido

indices, knn_graph = graph(X,knn,mutual=False)
W = adjacency_matrix(X, knn_graph, sigma, True)
L, D = laplacian(W, flag=lflag)
vals, vecs, vecs_k = eigen_Lap(L,kclust,lflag)

El grafo creado

plot_graph(X,knn_graph)

Análisis espectral. Observa el tipo de Laplaciano que usamos ($L$, $L_{\text{sym}}$ ó $L_{\text{rw}}$)

rvals = np.round(vals,3)
rvecs = np.round(vecs,3)

nv = 10
fig = plt.figure(figsize=(15,15))
plt.subplots_adjust(hspace = .5)
fig.add_subplot(321)
plt.title('valores propios', fontsize=14)
plt.scatter(range(nv),rvals[:nv])
fig.add_subplot(322)
plt.title('eigenvector 1', fontsize=14)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,0],cl=y))
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette, legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(323)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,1],cl=y))
plt.title('eigenvector 2', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(324)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,2],cl=y))
plt.title('eigenvector 3', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(325)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,3],cl=y))
plt.title('eigenvector 4', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(326)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,4],cl=y))
plt.title('eigenvector 5', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True);

Ahora, observa los subgrafos que se identifican solamente con la información de los vectores propios del Laplaciano. En la gráfica se muestra con un círculo, el subgrafo formado con los valores más grandes del vector (indicador) propio correspondiente k_vec

k_vec = 0 #el subgrafo correspondiente a algún valor propio 0
vec_i = rvecs[:,k_vec]
un = np.unique(vec_i)
np.where(vec_i==un[0])[0]
ind_i = np.zeros(vec_i.shape)
for i in range(un.shape[0]):
    ind_i[np.where(vec_i==un[i])[0]] = i

data_spec = pd.DataFrame(dict(x1 = X[:,0], x2 = X[:,1], cl = ind_i))
plot_graph(X, knn_graph, data_toy = data_spec, palet = sns.color_palette(n_colors=len(un)))

zeros = pd.DataFrame(X).iloc[np.where(vec_i==np.max(vec_i))[0]]
plt.scatter(zeros.iloc[:,0], zeros.iloc[:,1], s=300, linewidth=1, facecolors = 'none', edgecolors='black');

Finalmente, realizamos $k-$means con el embedding obtenido

# kmeans
kmeans = cluster.KMeans(n_clusters=kclust, init='random',random_state=0, n_init='auto')
y_km = kmeans.fit_predict(vecs_k)
data_km = pd.DataFrame(dict(x1=X[:,0],x2=X[:,1],cl = y_km))

fig = plt.figure(figsize=(15,7))
fig.add_subplot(121)
plt.title('Spectral clustering')
sns.scatterplot(x='x1', y='x2', data = data_km, hue='cl', s=150, 
            palette = custom_palette,legend = 'brief')
fig.add_subplot(122)
plt.title('Original')
sns.scatterplot(x='x1', y='x2', hue = 'cl', data = data_toy, palette=custom_palette, s=150)

<Axes: title={'center': 'Original'}, xlabel='x1', ylabel='x2'>

Ejemplo 3

ndata = 150
X, y, custom_palette, kclust = get_dataset('spirals', ndata)

data_toy = pd.DataFrame(X)
data_toy.columns = ['x1','x2']
data_toy = pd.DataFrame(data_toy).assign(cl = y)
sns.relplot(x='x1', y='x2', data = data_toy, height=5, s=60)
plt.title('Datos sintéticos', fontsize=10);

Parámetros para clústering espectral

knn = 10 # k-vecinos cercanos para la construcción del grafo
sigma = 1.5 # sigma del Kernel Gaussiano
lflag = 'rw' # Tipo de Laplaciano

Realiza el embedding de los datos según el Laplaciano inducido por el grafo construido

indices, knn_graph = graph(X,knn,mutual=False)
W = adjacency_matrix(X, knn_graph, sigma, True)
L, D = laplacian(W, flag=lflag)
vals, vecs, vecs_k = eigen_Lap(L,kclust,lflag)

El grafo creado

plot_graph(X,knn_graph)

Matriz de Adyacencias o Afinidad

plt.figure(figsize=(7,5))
sns.heatmap(knn_graph, cmap="YlGnBu");

Matriz de adyacencias (afinidad) sin pesos. Solo muestra los componentes están conectados

plt.figure(figsize=(7,5))
sns.heatmap(W, cmap="YlGnBu");

Matriz de adyacencias (afinidad) pesada usando distancia Gaussiana, es decir, con pesos $w_{i,j}=e^{\frac{-\Vert \mathbf{x}_i-\mathbf{x}_j \Vert^2}{2\sigma^2}}$ si $\mathbf{x}_i$ y $\mathbf{x}_j$ se conectan.

Análisis espectral. Observa el tipo de Laplaciano que usamos ($L$, $L_{\text{sym}}$ ó $L_{\text{rw}}$)

rvals = np.round(vals,3)
rvecs = np.round(vecs,3)

nv = 15
fig = plt.figure(figsize=(15,15))
plt.subplots_adjust(hspace = .5)
fig.add_subplot(321)
plt.title('valores propios', fontsize=14)
plt.scatter(range(nv),rvals[:nv])
fig.add_subplot(322)
plt.title('eigenvector 1', fontsize=14)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,0],cl=y))
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette, legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(323)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,1],cl=y))
plt.title('eigenvector 2', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(324)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,2],cl=y))
plt.title('eigenvector 3', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(325)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,3],cl=y))
plt.title('eigenvector 4', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True)
fig.add_subplot(326)
data_vecs = pd.DataFrame(dict(x1=range(rvecs.shape[0]),x2=rvecs[:,4],cl=y))
plt.title('eigenvector 5', fontsize=14)
sns.lineplot(x='x1', y='x2', data = data_vecs, hue='cl', palette = custom_palette,legend = 'brief',
               style = 'cl', markers = True);

Ahora, observa los subgrafos que se identifican solamente con la información de los vectores propios del Laplaciano. En la gráfica se muestra con un círculo, el subgrafo formado con los valores más grandes del vector (indicador) propio correspondiente k_vec

k_vec = 0 #el subgrafo correspondiente a algún valor propio 0
vec_i = rvecs[:,k_vec]
un = np.unique(vec_i)
np.where(vec_i==un[0])[0]
ind_i = np.zeros(vec_i.shape)
for i in range(un.shape[0]):
    ind_i[np.where(vec_i==un[i])[0]] = i

data_spec = pd.DataFrame(dict(x1 = X[:,0], x2 = X[:,1], cl = ind_i))
plot_graph(X, knn_graph, data_toy = data_spec, palet = sns.color_palette(n_colors=len(un)))

zeros = pd.DataFrame(X).iloc[np.where(vec_i==np.max(vec_i))[0]]
plt.scatter(zeros.iloc[:,0], zeros.iloc[:,1], s=300, linewidth=1, facecolors = 'none', edgecolors='black');

Finalmente, realizamos $k-$means con el embedding obtenido

# kmeans
kmeans = cluster.KMeans(n_clusters=kclust, init='random',random_state=0, n_init = 'auto')
y_km = kmeans.fit_predict(vecs_k)
data_km = pd.DataFrame(dict(x1=X[:,0],x2=X[:,1],cl = y_km))

fig = plt.figure(figsize=(12,5))
fig.add_subplot(121)
plt.title('Spectral clustering')
sns.scatterplot(x='x1', y='x2', data = data_km, hue='cl', s=150, 
            palette = custom_palette,legend = 'brief')
fig.add_subplot(122)
plt.title('Original')
sns.scatterplot(x='x1', y='x2', hue = 'cl', data = data_toy, palette=custom_palette, s=150);

¿Cómo es el embedding? La representación de nuestros datos inducido por el Laplaciano.

data_vecs = pd.DataFrame(np.hstack((rvecs[:,:5],y.reshape([y.shape[0],1]))))
data_vecs.columns = ['e1','e2','e3','e4','e5','cl']

El embedding está dado por los vectores propios asociados a los valores propios más pequeños...

sns.pairplot(data_vecs,diag_kind=None, hue='cl', palette = custom_palette, kind='scatter');

Spectral Clustering con sklearn

aff = 'nearest_neighbors'
#aff = 'rbf'
n_neigh = knn #12
sig = 1./sigma #5 
model = cluster.SpectralClustering(n_clusters=kclust,eigen_solver='arpack', affinity = aff, gamma = sig, n_neighbors = n_neigh).fit(X)

y_sc = model.labels_

La función es SpectralClustering, del módulo cluster de sklearn. Tenemos varias opciones para la matriz de afinidades, principalmente: - nearest_neighbors - rbf - precomputed Checa la ayuda...

Matriz de Afinidades

if aff == 'nearest_neighbors':
    w = model.affinity_matrix_.toarray()
else:
    w = model.affinity_matrix_

plt.figure(figsize=(7,5))
sns.heatmap(w, cmap="YlGnBu")

<Axes: >

data_sc = pd.DataFrame(dict(x1=X[:,0], x2=X[:,1], cl_sc = y_sc))
sns.relplot(x='x1', y='x2', data = data_sc, hue='cl_sc', height=5, palette = custom_palette, s = 150)
plt.title('Spectral Clustering', fontsize=10)

Text(0.5, 1.0, 'Spectral Clustering')

El embedding con SpectralEmbedding de sklearn.manifold

from sklearn.manifold import SpectralEmbedding

model2 = SpectralEmbedding(n_components=4,affinity='nearest_neighbors',gamma=sigma,eigen_solver='arpack',
                           n_neighbors=knn).fit(X)

plt.figure(figsize=(7,5))
w2 = model2.affinity_matrix_.toarray()
sns.heatmap(w2, cmap="YlGnBu")

<Axes: >

data_vecs_se = pd.DataFrame(dict(x1=model2.embedding_[:,0],x2=model2.embedding_[:,1],
                                 x3=model2.embedding_[:,2],x4=model2.embedding_[:,3],cl=y))
sns.pairplot(data_vecs_se,diag_kind=None, hue='cl', palette = custom_palette, kind='scatter');